// 2025/3/20
// https://leetcode.cn/problems/generate-parentheses/description/?envType=study-plan-v2&envId=top-100-liked
// 括号生成

class Solution {
    public:
        string tmp;
        vector<string> ans;
        int count;
    
        void dfs(int n)
        {
            if(n == 0 && count == 0)
            {
                ans.push_back(tmp);
                return;
            }
            else if(n > 0)
            {
                tmp.push_back('(');
                count++;
                dfs(n - 1);
                count--;
                tmp.pop_back();
            }
    
            if(count > 0)
            {
                tmp.push_back(')');
                count--;
                dfs(n);
                count++;
                tmp.pop_back();
            }
        }
    
        vector<string> generateParenthesis(int n) {
            count = 0;
            dfs(n);
            return ans;
        }
    };